package 笔试.乐金祥;

/**
 * @author:谢君臣
 * @Date:2021/8/31-19:32
 * @version:1.0
 * @function:
 */
public class Main {
    public static void main(String[] args) {
        int total = 12;
        int [] arr = new int[]{2, 5, 6, 7};
        System.out.println(solution(total,arr,arr.length-1,0));
    }
    public static int solution(int total,int [] arr,int i,int count){
        if (total==0)return count;
        else {
            if (i<0||total<0) return -1;
            else {
                int i1 = solution(total, arr, i - 1, count);
                int i2 = solution(total-arr[i], arr, i , count+1);
                int temp =0;
                if (i1>0&&i2>0)temp = Math.min(i1,i2);
                else temp = Math.max(i1,i2);
                return temp;
            }
        }
    }
    public class Solution {
        public int coinChange(int[] coins, int amount) {
            if (amount < 1) {
                return 0;
            }
            return coinChange(coins, amount, new int[amount]);
        }

        private int coinChange(int[] coins, int rem, int[] count) {
            if (rem < 0) {
                return -1;
            }
            if (rem == 0) {
                return 0;
            }
            if (count[rem - 1] != 0) {
                return count[rem - 1];
            }
            int min = Integer.MAX_VALUE;
            for (int coin : coins) {
                int res = coinChange(coins, rem - coin, count);
                if (res >= 0 && res < min) {
                    min = 1 + res;
                }
            }
            count[rem - 1] = (min == Integer.MAX_VALUE) ? -1 : min;
            return count[rem - 1];
        }
    }
}
